<TITLE>prob013: progressive party problem</TITLE>
<HR><!------------------------------------------------------------------------>
<CENTER>
<H1>prob013: progressive party problem</H1>

<TABLE>
<TR> <TD> proposed by
     <TD ALIGN=LEFT> <A HREF="http://www.cs.york.ac.uk/~tw">
          <B>Toby Walsh</B></A> 
          <ADDRESS><a href="mailto:tw@cs.york.ac.uk">
          tw@cs.york.ac.uk</a></ADDRESS>
</TABLE>
</CENTER>
<HR><!------------------------------------------------------------------------>
<H3> Specification </H3>

<TT>

The problem is to timetable a party at a yacht club. 
Certain boats are to be designated hosts, and the
crews of the remaining boats in turn visit the host boats for several
successive half-hour periods.  The crew of a host boat remains on
board to act as hosts while the crew of a guest boat together visits
several hosts.  Every boat can only host a limited number of guests at
a time (its capacity) and crew sizes are different. The table with
boat capacities and crew sizes can be found below; there were six time
periods.  A guest boat cannot not revisit a host and guest crews
cannot meet more than once.  The problem facing the rally organizer is
that of minimizing the number of host boats.
<P>



<center>
<table border>
<tr>
<td> boat number <td> capacity <td> crew size
<tr>
<td> 1 <td> 6 <td> 2 
<tr>
<td> 2 <td> 8 <td> 2 
<tr>
<td> 3 <td> 12 <td> 2 
<tr>
<td> 4 <td> 12 <td> 2  
<tr>
<td> 5 <td> 12 <td> 4 
<tr>
<td> 6 <td> 12 <td> 4 
<tr>
<td> 7 <td> 12 <td> 4 
<tr>
<td> 8 <td> 10 <td> 1 
<tr>
<td> 9 <td> 10 <td> 2 
<tr>
<td> 10 <td> 10 <td> 2 
<tr>
<td> 11 <td> 10 <td> 2 
<tr>
<td> 12 <td> 10 <td> 3 
<tr>
<td> 13 <td> 8 <td> 4 
<tr>
<td> 14 <td> 8 <td> 2 
<tr>
<td> 15 <td> 8 <td> 3  
<tr>
<td> 16 <td> 12 <td> 6 
<tr>
<td> 17 <td> 8 <td> 2 
<tr>
<td> 18 <td> 8 <td> 2 
<tr>
<td> 19 <td> 8 <td> 4 
<tr>
<td> 20 <td> 8 <td> 2 
<tr>
<td> 21 <td> 8 <td> 4 
<tr>
<td> 22 <td> 8 <td> 5 
<tr>
<td> 23 <td> 7 <td> 4 
<tr>
<td> 24 <td> 7 <td> 4 
<tr>
<td> 25 <td> 7 <td> 2 
<tr>
<td> 26 <td> 7 <td> 2 
<tr>
<td> 27 <td> 7 <td> 4 
<tr>
<td> 28 <td> 7 <td> 5 
<tr>
<td> 29 <td> 6 <td> 2 
<tr>
<td> 30 <td> 6 <td> 4 
<tr>
<td> 31 <td> 6 <td> 2 
<tr>
<td> 32 <td> 6 <td> 2 
<tr>
<td> 33 <td> 6 <td> 2 
<tr>
<td> 34 <td> 6 <td> 2 
<tr>
<td> 35 <td> 6 <td> 2 
<tr>
<td> 36 <td> 6 <td> 2 
<tr>
<td> 37 <td> 6 <td> 4 
<tr>
<td> 38 <td> 6 <td> 5 
<tr>
<td> 39 <td> 9 <td> 7 
<tr>
<td> 40 <td> 0 <td> 2 
<tr>
<td> 41 <td> 0 <td> 3 
<tr>
<td> 42 <td> 0 <td> 4 
</table>
</CENTER>

</TT>


<HR><!------------------------------------------------------------------------>

<UL>

 <A HREF="../../index.html"> Back</A> to CSPLib home page.


